package com.kehao.newcoder;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class NC121Solution {


    private char[] tmp;
    private Set<String> result = new HashSet<>();
    public ArrayList<String> Permutation(String str) {
        tmp = str.toCharArray();
        result.clear();
        LinkedList<Character> list = new LinkedList<>();
        for (int i = 0; i < tmp.length; i++) {
            list.add(tmp[i]);
        }
        dfs(list,0,str.length()-1);
        return new ArrayList<>(result);
    }

    private void dfs(LinkedList<Character> list, int depth, int threhold) {
        if(depth==threhold){
            tmp[depth] = list.get(0);
            String s = new String(tmp);
            result.add(s);
            return;
        }
        for (int i = 0; i < list.size(); i++) {
            tmp[depth] = list.get(i);
            Character remove = list.remove(i);
            dfs(list,depth+1,threhold);
            list.add(i,remove);
        }
    }


    @Test
    public void test(){
        Permutation("aab");
    }
}
